package com.seu.algorithms.sorting.others;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author liangfeihu
 * @since 2018/12/12 11:31
 */
public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        // 起始下沉的位置：应该从最后一个节点(n-1)的父节点(n-1-1)/2开始
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            // 下沉操作 siftDown(i);
            heapify(arr, i, len);
        }
    }

    /**
     * 递归法实现下沉操作
     *
     * @param arr
     * @param i
     * @param len
     */
    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            // 递归，直到数组最后一个元素
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        if (i != j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public static void main(String[] args) throws Exception {
        System.out.println((int) Math.floor(8 / 2));
        System.out.println((int) Math.floor(7 / 2));
        System.out.println((int) Math.floor(6 / 2));

        int[] array = {3, 5, 6, 8, 1, 9, 2, 7};
        print(array);
        HeapSort sort = new HeapSort();
        int[] sort1 = sort.sort(array);

        print(sort1);

    }

    public static void print(int[] array) {
        int length = array.length;
        for (int i = 0; i < length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }

}
